364D - Ghd - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;
#define For(Ti,Ta,Tb) for(int Ti=(Ta);Ti<=(Tb);++Ti)
#define Dec(Ti,Ta,Tb) for(int Ti=(Ta);Ti>=(Tb);--Ti)
#define Debug(...) fprintf(stderr,__VA_ARGS__)
using ll=long long;
mt19937 eng(chrono::system_clock::now().time_since_epoch().count());
template<typename T> T Rand(const T &_l,const T &_r){return uniform_int_distribution<T>(_l,_r)(eng);}
vector<pair<ll,int>> PrimeFac(ll _x){
	vector<pair<ll,int>> _res;
	auto _add=[&](int _i){
		if(_x%_i==0){
			_res.emplace_back(_i,0);
			while(_x%_i==0) ++_res.back().second,_x/=_i;
		}
	};
	_add(2),_add(3);
	for(int _i=5;1LL*_i*_i<=_x;_i+=6) _add(_i),_add(_i+2);
	if(_x>1) _res.emplace_back(_x,1);
	return _res;
}
vector<ll> Divisors(ll _x){
	vector<ll> _res;
	for(int _i=1;1LL*_i*_i<=_x;++_i) if(_x%_i==0){
		_res.push_back(_i);
		if(1LL*_i*_i!=_x) _res.push_back(_x/_i);
	}
	return _res;
}
const int N=1e6+5;
int n;ll a[N];
int main(){
	ios::sync_with_stdio(false),cin.tie(nullptr);
	cin>>n;
	For(i,1,n) cin>>a[i];
	ll ans=1;
	For(_,1,12){
		int i=Rand(1,n);
		auto pf=PrimeFac(a[i]);
		auto div=Divisors(a[i]);
		sort(div.begin(),div.end(),greater<ll>());
		map<ll,int,greater<ll>> cnt;
		For(j,1,n) ++cnt[__gcd(a[j],a[i])];
		for(auto x:pf) for(ll y:div) if(a[i]%(y*x.first)==0) cnt[y]+=cnt[y*x.first];
		for(auto x:cnt){
			if(ans>x.first) break;
			if(x.second>=(n+1)/2){
				ans=max(ans,x.first);break;
			}
		}
	}
	cout<<ans<<'\n';
	#ifdef zyz
		Debug("Elapsed time: %dms\n",int(clock()));
	#endif
	return 0;
}//16767234565894488865